#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        vector<char> stacks;
        char tmp;
        int i;
        if(s.size()==0) return true;
        if(s.size()==1) return false;

        for (i = 0; i < s.size(); ++i) {
            if (isLift(s[i])) {
                stacks.push_back(s[i]);
            }
            else{
                if(stacks.empty()){
                    return false;
                }
                tmp = stacks.back();
                stacks.pop_back();
                if (!isRight(tmp, s[i]))
                    break;
            }
        }

        if(i!=s.size() || !stacks.empty()){
            return false;
        }
        else
            return true;

    }
    bool isLift(char c){
        switch (c) {
            case '(':
                return true;
                break;
            case '[':
                return true;
                break;
            case '{':
                return true;
                break;
            default:
                return false;
                break;
        }
    }
    bool isRight(char c1, char c2){
        switch (c1) {
            case '(':
                if(c2 == ')')
                    return true;
                else
                    return false;
                break;
            case '[':
                if(c2 == ']')
                    return true;
                else
                    return false;
                break;
            case '{':
                if(c2 == '}')
                    return true;
                else
                    return false;
                break;
            default:
                return false;
                break;
        }
    }
};

int main(int argc, char**){
    Solution solu = Solution();
    // string str("()[]{}");
    // string str = "()[]{}";
    string str = "){";
    cout<< solu.isValid(str) <<endl;

    return 0;
}